package 八皇后问题;

public class 八皇后问题 {
	
	//八皇后棋盘可以用一个一维数组表示，下标表示第几行 (第几个皇后)，数字表示第几列 (放的位置)
	//因为每一行只放一个皇后，所以不会在同一行冲突。
	
	//定义皇后数量
	static int max = 8;
	//定义皇后拜访位置
	static int[] arr = new int[max];
	//记录共有几个解
	static int count = 0;
	public static void main(String[] args) {
		//测试
		八皇后问题 queen8 = new 八皇后问题();
		//从第一个皇后开始，第一行第一列
		queen8.check(0);
		//共有几个解
		System.out.println("8皇后共有 "+ count +" 种解法。");
		
	}
	
	
	/**
	 * 放置皇后
	 * @param n 第几个皇后
	 */
	public void check(int n) {
		//System.out.println(n);
		if(n == max) {
			//max=8表示已经放好第8个皇后了，因为arr[8]是第九个
			show();
			return;
		}
		
		//放入皇后，并判断冲突
		for(int i = 0 ; i < max ; i++) {
			//先把第 n 个皇后放到第 i 列，行下标表示第几个皇后，数值表示第几列
			arr[n] = i;
			//判断是否冲突
			if(judge(n)) {
				//不冲突，就放置下一个，开始递归
				check(n+1);
			}
			//如果冲突，不进入if，直接放到下一列
		}
	}
	
	
	/** 
	 * 判断当前皇后摆放位置是够冲突
	 * @param n 表示第几个皇后
	 * @return
	 */
	public boolean judge(int n) {
		
		//将当前皇后位置与之前摆放好的皇后进行比较(数组中保存了已经摆放好了的皇后)
		for(int i = 0; i < n; i++) {
			//是否与之前的列冲突，就是是不是同一列，arr[i] == arr[n]
			//是否与之前同一对角线，方法是对角线上两个点，做垂线，形成等腰直角三角形，
			//这两个点离垂线焦点 距离相等，行 == 列
			/*
			   0 0 0 0 
			   1 1 2 0
			   1 0 0 0
			   2 0 0 0
			   
			   2与2之间两腰相等,行 == 列
			 */
			if(arr[i] == arr[n] || Math.abs(n-i)==Math.abs(arr[n]-arr[i]) ) {
				//说明发生冲突
				return false;
			}
		}
		//否则不冲突
		return true;
	}
	
	/**
	 * 输出数组
	 */
	public void show() {
		//输出一次结果，记录一次
		count++;
		for(int i = 0; i < arr.length; i++ ) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
}
